  
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">















 
 
 
 
 
 
 
  
  


<html>
  <head>
    <script type="text/javascript" language="JavaScript">
    ORIGINAL_PAGE_PATH = "/appengine/articles/geosearch.html";
    </script>
    
    
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<title>24 hours in SF: A Geolocation App - Google App Engine - Google Code</title>
<script type="text/javascript"><!--
(function(){function a(){this.t={};this.tick=function(c){this.t[c]=(new Date).getTime()};this.tick("start")}var b=new a;window.jstiming={Timer:a,load:b};if(window.external&&window.external.pageT)window.jstiming.pt=window.external.pageT;})();

var _tocPath_ = '/appengine/docs/_toc.ezt';
var codesite_token = null;
//--></script>
<link href="../../css/codesite.pack.04102009.css" type="text/css" rel="stylesheet"></link>
<script src="../../js/codesite_head.pack.04102009.js" type="text/javascript"></script>
<script type="text/javascript">CODESITE_CSITimer['load'].tick('bhs');</script>
<link rel="search" type="application/opensearchdescription+xml" title="Google Code" href="http://code.google.com/osd.xml" />

<!--[if IE]><link rel="stylesheet" type="text/css" href="../../css/iehacks.css" /><![endif]-->

    <link href="../../css/semantic_headers.css" rel="stylesheet" type="text/css" />
    <link href="../css/local_extensions.css" rel="stylesheet" type="text/css" />
  </head>

  <body class="gc-documentation">

    
    
    
</a>

<div id="gb">
 <span>
  
    <a id="lang-dropdown" class="dropdown" href="http://code.google.com" onclick="return false;"><img class="globeicon" src="../../images/globe2_small.png"/><span>English</span></a>
  
 </span>
</div>

<div class="gbh" style="left: 0pt;"></div>
<div class="gbh" style="right: 0pt;"></div>


<style type="text/css">
  #gc-topnav h1 {
    padding: 0 0 0 6px;
  }
</style>


<div id="gc-container">
<a name="top"></a>
<div id="skipto">
  <a href="#gc-pagecontent-anchor">Skip to page content</a>
  <a href="#gc-toc-anchor">Skip to main navigation</a>
</div>

<div id="gc-header">
  <div id="logo"><a href="http://code.google.com">
  
  
     <img src="../../images/cleardot.gif" height="1px" width="1px" alt="Google Code Home Page" id="gc-logo-img"/>
  
  
  </a></div>
  <div id="search">
    <div id="searchForm" class="searchForm">
      <form id="cse" action="http://www.google.com/cse" accept-charset="utf-8" class="gsc-search-box" onsubmit="executeGSearch(document.getElementById('gsearchInput').value); return false;">
      <noscript>
      <input type="hidden" name="cref" value="http://code.google.com/cse/googlecode-context.xml"/>
      </noscript>
        <table class="gsc-search-box" cellpadding="0" cellspacing="0">
          <tbody>
            <tr>
              <td class="gsc-input">
                <input id="gsearchInput" type="text" name="q" maxlength="2048" class="gsc-input" autocomplete="off" title="Google Code Search" style="width:345px"/>
              </td>
              <td class="gsc-search-button">
                <div id="cs-searchresults" onclick="event.cancelBubble = true;"></div>
                <input title="Search" id="gsearchButton" class="gsc-search-button" name="sa" value="Search" type="submit"/>
              </td>
            </tr>
            <tr>
              <td colspan="2" class="greytext">e.g. "templates" or "datastore"</td>
            </tr>
          </tbody>
        </table>
      </form>
    </div> <!-- end searchForm -->
  </div> <!-- end search -->
</div> <!-- end gc-header -->


<div id="codesiteContent">

<a name="gc-topnav-anchor"></a>
<div id="gc-topnav">
  <h1>Google App Engine</h1>
  <ul id="articles" class="gc-topnav-tabs">

    <li id="home_link">
      <a href="../index.html" title="Google App Engine home page">Home</a>
    </li>
  
    <li id="docs_link">
      <a href="../docs/index.html" title="Official Google App Engine documentation">Docs</a>
    </li>
  
    <li id="faq_link">
      <a href="../kb/index.html" title="Answers to frequently asked questions about Google App Engine">FAQ</a>
    </li>
  
    <li id="articles_link">
      <a href="index.html" class="selected" title="Focused articles and tutorials for Google App Engine developers">Articles</a>
    </li>
  
    <li>
      <a href="http://googleappengine.blogspot.com/" title="Official Google App Engine blog">Blog</a>
    </li>
  
    <li>
      <a href="../community.html" title="Community home for Google App Engine">Community</a>
    </li>
  
    <li>
      <a href="../terms.html" title="Google App Engine terms of service">Terms</a>
    </li>
  
    <li>
      <a href="../downloads.html" title="Download Google App Engine">Download</a>
    </li>
  

  </ul>
</div> <!-- end gc-topnav -->

    <div class="g-section g-tpl-170">

      <a name="gc-toc-anchor"></a>  
      <div class="g-unit g-first" id="gc-toc">
        <ul>
  <li><a href="../downloads.html">Downloads</a></li>
  <li><a href="http://code.google.com/status/appengine">System Status</a></li>
  <li><a href="http://code.google.com/p/googleappengine/issues/list">Issue Tracker</a></li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Getting Started</h2>
    <ul>
      <li><a href="../docs/whatisgoogleappengine.html">What Is Google App Engine?</a></li>
      <li><a href="../docs/java/gettingstarted/index.html">Java</a>
        <ul>
              <li><a href="../docs/java/gettingstarted/introduction.html">Introduction</a></li>
    <li><a href="../docs/java/gettingstarted/installing.html">Installing the Java SDK</a></li>
    <li><a href="../docs/java/gettingstarted/creating.html">Creating a Project</a></li>
    <li><a href="../docs/java/gettingstarted/usingusers.html">Using the Users Service</a></li>
    <li><a href="../docs/java/gettingstarted/usingjsps.html">Using JSPs</a></li>
    <li><a href="../docs/java/gettingstarted/usingdatastore.html">Using the Datastore with JDO</a></li>
    <li><a href="../docs/java/gettingstarted/staticfiles.html">Using Static Files</a></li>
    <li><a href="../docs/java/gettingstarted/uploading.html">Uploading Your Application</a></li>

        </ul>
      </li>
      <li><a href="../docs/python/gettingstarted/index.html">Python</a>
        <ul>
            <li><a href="../docs/python/gettingstarted/introduction.html">Introduction</a></li>
  <li><a href="../docs/python/gettingstarted/devenvironment.html">The Development Environment</a></li>
  <li><a href="../docs/python/gettingstarted/helloworld.html">Hello, World!</a></li>
  <li><a href="../docs/python/gettingstarted/usingwebapp.html">Using the webapp Framework</a></li>
  <li><a href="../docs/python/gettingstarted/usingusers.html">Using the Users Service</a></li>
  <li><a href="../docs/python/gettingstarted/handlingforms.html">Handling Forms With webapp</a></li>
  <li><a href="../docs/python/gettingstarted/usingdatastore.html">Using the Datastore</a></li>
  <li><a href="../docs/python/gettingstarted/templates.html">Using Templates</a></li>
  <li><a href="../docs/python/gettingstarted/staticfiles.html">Using Static Files</a></li>
  <li><a href="../docs/python/gettingstarted/uploading.html">Uploading Your Application</a></li>

        </ul>
      </li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Java <sup class="new">Early Look</sup></h2>
    <ul>
          <li><a href="../docs/java/overview.html">Overview</a></li>
    <li><a href="../docs/java/runtime.html">Servlet Environment</a></li>
    <li><a href="../docs/java/datastore/index.html">Storing Data</a>
      <ul>
            <li><a href="../docs/java/datastore/overview.html">Overview</a></li>
    <li><a href="../docs/java/datastore/usingjdo.html">Using JDO</a></li>
    <li><a href="../docs/java/datastore/dataclasses.html">Defining Data Classes</a></li>
    <li><a href="../docs/java/datastore/creatinggettinganddeletingdata.html">Creating, Getting and Deleting Data</a></li>
    <li><a href="../docs/java/datastore/queriesandindexes.html">Queries and Indexes</a></li>
    <li><a href="../docs/java/datastore/transactions.html">Transactions</a></li>
    <li><a href="../docs/java/datastore/relationships.html">Relationships</a></li>
    <li><a href="../docs/java/datastore/usingjpa.html">Using JPA</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/datastore/package-summary.html">Low-level API</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/apis.html">Services</a>
      <ul>
        <li><a href="../docs/java/memcache/index.html">Memcache</a>
          <ul>
                <li><a href="../docs/java/memcache/overview.html">Overview</a></li>
    <li><a href="../docs/java/memcache/usingjcache.html">Using JCache</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/memcache/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/urlfetch/index.html">URL Fetch</a>
          <ul>
                <li><a href="../docs/java/urlfetch/overview.html">Overview</a></li>
    <li><a href="../docs/java/urlfetch/usingjavanet.html">Using java.net</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/urlfetch/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/mail/index.html">Mail</a>
          <ul>
                <li><a href="../docs/java/mail/overview.html">Overview</a></li>
    <li><a href="../docs/java/mail/usingjavamail.html">Using JavaMail</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/mail/package-summary.html">Low-level API</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/images/index.html">Images</a>
          <ul>
                <li><a href="../docs/java/images/overview.html">Overview</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/images/package-summary.html">API Reference</a></li>

          </ul>
        </li>
        <li><a href="../docs/java/users/index.html">Google Accounts</a>
          <ul>
                <li><a href="../docs/java/users/overview.html">Overview</a></li>
    <li><a href="../docs/java/javadoc/com/google/appengine/api/users/package-summary.html">API Reference</a></li>

          </ul>
        </li>
      </ul>
    </li>
    <li><a href="../docs/java/javadoc/index.html">Javadoc Reference</a></li>
    <li><a href="../docs/java/jrewhitelist.html">JRE Class White List</a></li>
    <li><a href="../docs/java/config/index.html">Configuration</a>
      <ul>
            <li><a href="../docs/java/config/webxml.html">Deployment Descriptor</a></li>
    <li><a href="../docs/java/config/appconfig.html">App Config</a></li>
    <li><a href="../docs/java/config/indexconfig.html">Index Config</a></li>
    <li><a href="../docs/java/config/cron.html">Scheduled Tasks</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/tools/index.html">Tools</a>
      <ul>
            <li><a href="../docs/java/tools/devserver.html">Development Server</a></li>
    <li><a href="../docs/java/tools/uploadinganapp.html">Uploading and Managing</a></li>
    <li><a href="../docs/java/tools/eclipse.html">Google Plugin for Eclipse</a></li>
    <li><a href="../docs/java/tools/ant.html">Using Apache Ant</a></li>

      </ul>
    </li>
    <li><a href="../docs/java/howto/index.html">How-To</a>
      <ul>
              <li><a href="../docs/java/howto/unittesting.html">Unit Testing</a></li>

      </ul>
    </li>

    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Python</h2>
    <ul>
          <li><a href="../docs/python/overview.html">Overview</a></li>
    <li><a href="../docs/python/runtime.html">CGI Environment</a></li>
    <li><a href="../docs/python/datastore/index.html">Storing Data</a>
      <ul>
             <li><a href="../docs/python/datastore/overview.html">Overview</a></li>
     <li><a href="../docs/python/datastore/entitiesandmodels.html">Entities and Models</a></li>
     <li><a href="../docs/python/datastore/creatinggettinganddeletingdata.html">Creating, Getting and Deleting Data</a></li>
     <li><a href="../docs/python/datastore/keysandentitygroups.html">Keys and Entity Groups</a></li>
     <li><a href="../docs/python/datastore/queriesandindexes.html">Queries and Indexes</a></li>
     <li><a href="../docs/python/datastore/transactions.html">Transactions</a></li>
     <li><a href="../docs/python/datastore/typesandpropertyclasses.html">Types and Property Classes</a></li>
     <li><a href="../docs/python/datastore/gqlreference.html">GQL Reference</a></li>

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/datastore/modelclass.html">Model</a></li>
         <li><a href="../docs/python/datastore/expandoclass.html">Expando</a></li>
         <li><a href="../docs/python/datastore/polymodelclass.html">PolyModel</a></li>
         <li><a href="../docs/python/datastore/propertyclass.html">Property</a></li>
         <li><a href="../docs/python/datastore/queryclass.html">Query</a></li>
         <li><a href="../docs/python/datastore/gqlqueryclass.html">GqlQuery</a></li>
         <li><a href="../docs/python/datastore/keyclass.html">Key</a></li>
         <li><a href="../docs/python/datastore/functions.html">Functions</a></li>
         <li><a href="../docs/python/datastore/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

      </ul>
    </li>
    <li><a href="../docs/python/apis.html">Services</a>
      <ul>
        <li><a href="../docs/python/memcache/index.html">Memcache</a>
          <ul>
                 <li><a href="../docs/python/memcache/overview.html">Overview</a></li>
      <li><a href="../docs/python/memcache/usingmemcache.html">Using Memcache</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/memcache/clientclass.html">Client</a></li>
         <li><a href="../docs/python/memcache/functions.html">Functions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/urlfetch/index.html">URL Fetch</a>
          <ul>
                 <li><a href="../docs/python/urlfetch/overview.html">Overview</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/urlfetch/fetchfunction.html">The fetch Function</a></li>
         <li><a href="../docs/python/urlfetch/responseobjects.html">Response Objects</a></li>
         <li><a href="../docs/python/urlfetch/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/mail/index.html">Mail</a>
          <ul>
                 <li><a href="../docs/python/mail/overview.html">Overview</a></li>
     <li><a href="../docs/python/mail/sendingmail.html">Sending Mail</a></li>
     <li><a href="../docs/python/mail/attachments.html">Attachments</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/mail/emailmessageclass.html">EmailMessage</a></li>
         <li><a href="../docs/python/mail/emailmessagefields.html">Message Fields</a></li>
         <li><a href="../docs/python/mail/functions.html">Functions</a></li>
         <li><a href="../docs/python/mail/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/images/index.html">Images</a>
          <ul>
                 <li><a href="../docs/python/images/overview.html">Overview</a></li>
     <li><a href="../docs/python/images/installingPIL.html">Installing PIL</a></li>
     <li><a href="../docs/python/images/usingimages.html">Using the Images API</a></li>
     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/images/imageclass.html">Image</a></li>
         <li><a href="../docs/python/images/functions.html">Functions</a></li>
         <li><a href="../docs/python/images/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
        <li><a href="../docs/python/users/index.html">Google Accounts</a>
          <ul>
                 <li><a href="../docs/python/users/overview.html">Overview</a></li>
     <li><a href="../docs/python/users/userobjects.html">User Objects</a></li>
     <li><a href="../docs/python/users/loginurls.html">Login URLs</a></li>
     <li><a href="../docs/python/users/adminusers.html">Admin Users</a></li>

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/users/userclass.html">User</a></li>
         <li><a href="../docs/python/users/functions.html">Functions</a></li>
         <li><a href="../docs/python/users/exceptions.html">Exceptions</a></li>
       </ul>
     </li>

          </ul>
        </li>
      </ul>
    </li>
    <li><a href="../docs/python/config/index.html">Configuration</a>
      <ul>
            <li><a href="../docs/python/config/appconfig.html">App Config</a></li>
    <li><a href="../docs/python/config/indexconfig.html">Index Config</a></li>
    <li><a href="../docs/python/config/cron.html">Scheduled Tasks</a></li>

      </ul>
    </li>
    <li><a href="../docs/python/tools/index.html">Tools</a>
      <ul>
            <li><a href="../docs/python/tools/devserver.html">Development Server</a></li>
    <li><a href="../docs/python/tools/uploadinganapp.html">Uploading and Managing</a></li>
    <li><a href="../docs/python/tools/uploadingdata.html">Uploading Data</a></li>
    <li><a href="../docs/python/tools/webapp/index.html">webapp Framework</a>
      <ul>
             <li><a href="../docs/python/tools/webapp/overview.html">Overview</a></li>
     <li><a href="../docs/python/tools/webapp/running.html">Running the Application</a></li>
     <li><a href="../docs/python/tools/webapp/requesthandlers.html">Request Handlers</a></li>
     <li><a href="../docs/python/tools/webapp/requestdata.html">Request Data</a></li>
     <li><a href="../docs/python/tools/webapp/buildingtheresponse.html">Building the Response</a></li>
     <li><a href="../docs/python/tools/webapp/redirects.html">Redirects, Headers and Status Codes</a></li>
     

     <li><span class="tlw-title tlw-expanded">Reference</span>
       <ul>
         <li><a href="../docs/python/tools/webapp/requestclass.html">Request</a></li>
         <li><a href="../docs/python/tools/webapp/responseclass.html">Response</a></li>
         <li><a href="../docs/python/tools/webapp/requesthandlerclass.html">RequestHandler</a></li>
         <li><a href="../docs/python/tools/webapp/wsgiapplicationclass.html">WSGIApplication</a></li>
         <li><a href="../docs/python/tools/webapp/utilmodule.html">Utility Functions</a></li>
         
       </ul>
     </li>

      </ul>
    </li>
    <li><a href="../docs/python/tools/libraries.html">Third-party Libraries</a></li>

      </ul>
    </li>
    <li><a href="../docs/python/howto/index.html">How-To</a>
      <ul>
              <li><a href="../docs/python/howto/usinggdataservices.html">Google Data Services</a></li>

      </ul>
    </li>

    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Managing Your App</h2>
    <ul>
      <li><a href="../docs/theadminconsole.html">The Admin Console</a></li>
      <li><a href="../docs/quotas.html">Quotas</a></li>
      <li><a href="../docs/billing.html">Billing</a></li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><h2>Resources</h2>
    <ul>
      <li><a href="../kb/index.html">FAQ</a></li>
      <li><a href="index.html">Articles</a></li>
      <li><a href="http://appengine-cookbook.appspot.com/">Cookbook</a></li>
      <li><a href="http://appgallery.appspot.com/">App Gallery</a></li>
      <li><a href="http://code.google.com/p/googleappengine/">SDK Code</a></li>
      <li><a href="http://code.google.com/p/google-app-engine-samples/">Sample Apps Code</a></li>
      <li><a href="../community.html">Discussion Groups</a></li>
    </ul>
  </li>
</ul>
<div class="line"></div>
<ul>
  <li><a href="../docs/roadmap.html">Product Roadmap</a></li>
  <li><a href="http://code.google.com/p/googleappengine/wiki/SdkReleaseNotes">Release Notes</a></li>
  <li><a href="../docs/revision_history.html">Revision History</a></li>
</ul>

        <a class="hidden" href="#gc-topnav-anchor">More Google App Engine resource links</a>
      </div>
      
      <a name="gc-pagecontent-anchor"></a>   
      <div class="g-unit" id="gc-pagecontent">
        <script type="text/javascript">CODESITE_docEarlyProcessing();</script>
        <h1 class="page_title">24 hours in SF: A Geolocation App</h1>


<div id="jd-content">
<div class="jd-descr">
<i>Marzia Niccolai, Brett Slatkin App Engine Team</i><br>
<i>February 04, 2009</i>

<h2>Introduction</h2>
<p>Never knowing when a strike of inspiration will cause me to work until late at night (or early in to the morning), I always wanted an application that could tell me where I could grab a cup of coffee or bite to eat where I was, when I was looking, be it 1pm or 1am. So, I decided to write such an application, with the Google Gears Geo-Location API to determine location, geolocation to search for nearby businesses, and Google Maps for easy visualization.</p>

<p>To do geo-location with App Engine, we need to rethink normal database techniques, since the inherent query limitations of App Engine means we cannot do inequality filters on multiple properties, such as longitude and latitude.  This means that query-time computation of a location's bounding box is not possible.  We have been recommending people use <a href="http://en.wikipedia.org/wiki/Geohash">geohashing</a> for this problem up until this point. Geohashing takes a latitude and longitude position and generates a single string. We can find close points by doing string prefix matching. However, this technique does have limits, especially in certain parts of the world.</p>

<p>Another solution to this problem is to pre-compute the bounding boxes for a location at write time. Brett Slatkin, a Google engineer on the App Engine team, developed an <a href="http://code.google.com/p/mutiny">open source library</a> for pre-computing bounding boxes at write time.  We will use this library to develop our application: <a href="http://code.google.com/p/google-app-engine-samples/">24 hours in San Francisco</a>.</p>

<h2>Pre-Computing Bounding Boxes</h2>
<p>Traditionally, if you are looking for locations near a specific point, you do two inequality filters on the longitude and on the latitude for your query.  For instance in a MySQL database, such a query might look like:</p>
<pre class="prettyprint">SELECT *
FROM Business
WHERE Lat > (position_lat - d) AND
      Lat < (position_lat + d) AND
      Lon > (position_lon - d) AND
      Lon < (position_lon + d);</pre>
<p>This query searches for locations that are located in a box surrounding the search point:<br />
<img src="img/sf_onetile.png"></p>
<p>This won't work with App Engine, due to the way the datastore handles queries (see <a href="http://sites.google.com/site/io/under-the-covers-of-the-google-app-engine-datastore">Under the Covers of the App Engine Datastore</a>), only inequality filters on one property are supported.  However, a general strategy with App Engine is to compute at write time what would, in other systems, be computed during a query.</p>
<p>To do this, we assume that the world is pre-tiled with bounding boxes at different granularity.  When wish to add a new location in our application, we compute the bounding boxes that surround that location when we write that entity to the datastore, and store all of the relevant bounding boxes in a <code>ListProperty</code> that we can easily query.  If a location is sufficiently close to the edges of box, we may simply add the adjoining box to the list of relevant boxes.<br />
<img src="img/corner_map.png"></p>
<h2>Inputting a Location</h2>
<p>When we input a location for which we will later want to search, we do a series of computations before saving the data to the datastore to compute bounding boxes for different granularities.  We define a bounding box as two coordinates, the northwest corner of the box, and the southwest corner, and store this geobox as a string of <code>lat|lon|lat|lon</code> such as <code>"37.78452999999|-122.39532395324|37.78452999998|-122.39532395323"</code>.</p>
<p>The resolution is determined by the number of places after the decimal point our data source contains.  For example, 15 decimal-point values would be called "resolution 15". Each coordinate in the geobox must have all digits defined for its corresponding resolution. That means even trailing zeros should be present. In addition to a resolution, we also specify a "slice".  A slice is how finely to divide each level of resolution in the geobox.</p>
<p>We will compute a geobox for a point by figuring out the closest known geobox that surrounds the point at the current slice and resolution.  The <a href="http://code.google.com/p/mutiny/source/browse/trunk/geobox.py">source file</a> for the geobox library gives greater details on the algorithm.</p>
<p>For our application, we specify a set of (resolution, slice, compute_set) values, where compute_set is a boolean value indicating whether to search for a location in a single geoboxes, or a set of surrounding geoboxes. (For larger geoboxes, we don't need to examine adjacent geoboxes.)</p>
<pre class="prettyprint">GEOBOX_CONFIGS = (
  (4, 5, True),
  (3, 2, True),
  (3, 8, False),
  (3, 16, False),
  (2, 5, False),
)

def add(self, **kwargs):
  lat = kwargs.pop('lat')
  lon = kwargs.pop('lon')
  for (resolution, slice, use_set) in GEOBOX_CONFIGS:
    if use_set:
      all_boxes.extend(geobox.compute_set(lat, lon, resolution, slice))
    else:
      all_boxes.append(geobox.compute(lat, lon, resolution, slice))</pre>
<p>The methods <code>compute</code> and <code>compute_set</code> use the function <code>_round_slice_down</code> to do the actual bounding box calculation:</p>
<pre class="prettyprint">def _round_slice_down(coord, slice):
  try:
    remainder = coord % slice
    if coord > 0:
      return coord - remainder + slice
    else:
      return coord - remainder
  except decimal.InvalidOperation:
    # This happens when the slice is too small for the current coordinate.
    # That means we've already got zeros in the slice's position, so we're
    # already rounded down as far as we can go.
    return coord


def compute_tuple(lat, lon, resolution, slice):
  """Computes the tuple Geobox for a coordinate with a resolution and slice."""
  decimal.getcontext().prec = resolution + 3
  lat = decimal.Decimal(str(lat))
  lon = decimal.Decimal(str(lon))
  slice = decimal.Decimal(str(1.0 * slice * 10 ** -resolution))
 
  adjusted_lat = _round_slice_down(lat, slice)
  adjusted_lon = _round_slice_down(lon, slice)
  return (adjusted_lat, adjusted_lon - slice,
          adjusted_lat - slice, adjusted_lon)</pre>
<p>There are also a few other utility methods defined in the source file used to compute the geoboxes (such as to format the geobox strings as we explained above).  Once we generate a list of geobox strings, we simply store them in a <code>StringListProperty</code> and put our entity, along with the other information (human readable address, phone number, hours, etc), in the datastore.</p>
<h2>Querying for a location</h2>
<p>After we have uploaded all of our current business information to our application, we will allow our users to query for locations near their current location.  To do this, we take the user's current location (we explain how we get this information below), and construct a list of bounding boxes surrounding that location.  We then perform a series of queries to retrieve all nearby businesses, and sort those locations by distance from our user.</p>
<pre class="prettyprint">class Store(db.Model):

  @classmethod
  def query(self, lat, lon, max_results, min_params):
    """Queries for locations repeatedly until max results or scope is reached.
    Args:
      lat, lon: Coordinates of the agent querying.
      max_results: Maximum number of stops to find.
      min_params: Tuple (resolution, slice) of the minimum resolution to allow.

    Returns:
      List of (distance, store) tuples, ordered by minimum distance first.
      There will be no duplicates in these results. Distance is in meters.
    """
    ...
    for params in GEOBOX_CONFIGS:
      if len(found_stores) >= max_results:
        break
      if params < min_params:
        break

      resolution, slice, unused = params
      box = geobox.compute(lat, lon, resolution, slice)
      logging.info("Searching for box=%s at resolution=%s, slice=%s",
                    box, resolution, slice)
      query = self.all().filter("geoboxes =", box)
      results = query.fetch(50)
      logging.info("Found %d results", len(results))
    stores_by_distance = []

    for store in found_stores.itervalues():
      distance = _earth_distance(lat, lon, store.location.lat, store.location.lon)
      stores_by_distance.append((distance, store))
    stores_by_distance.sort()

    return stores_by_distance</pre>
<p>In our application's request handler, the call to query for the relevant stores is very easy:</p>
<pre class="prettyprint">def post(self):
  user_pos_lat = float(self.request.get('lat'))
  user_pos_lon = float(self.request.get('lon'))

  my_stores = Store.query(lat=user_pos_lat,
                          lon=user_pos_lon,
                          max_results=2, min_params=(2,0))</pre>
<p>And that's it!</p>
<h2>Using Google Gears & Maps</h2>
<p>To find and display a user's location, we use <a href="http://code.google.com/apis/gears/api_geolocation.html">Google Gear's Geolocation API</a>, and <a href="http://code.google.com/apis/maps/documentation/services.html#Geocoding">Google Map's Geocoding API</a>.  Both of these are client side techniques that use Javascript to get our user's lat/lon using GPS (if available) or a user entered address. We also use Google Maps to display the user location and all of the found business locations.</p>
<p>Using Javascript with App Engine doesn't require anything special, since it's executed on the client side. As with any application, we can include Javascript in our html templates. Working with Google Maps and Google Gears requires some basic Javascript and a couple of easy steps.  The complete code is available in the <a href="http://code.google.com/p/google-app-engine-samples/">svn repository</a>, but below we cover the basic steps for using Gears and Maps in our application.</p>
<h3>Get the User's Position</h3>
<p>When our page loads, we check if our user has Gears, and if so, get their position. If the user does not have gears, we can prompt them to install it. Since our application depends on knowing exactly where our user is, we set the option </code>enableHighAccuracy</code> in the <code>getPosition</code> function. This will make it more likely that we will get the user's GPS information if they have GPS enabled.  The function <code>getPosition</code> takes two arguments, <code>updatePosition</code>, which is a called if the location is found, and <code>handleError</code>, called when an error occurs.</p>
<pre class="prettyprint">function loadresources(){
  if (!window.google || !google.gears) {
    location.href = "http://gears.google.com/?action=install&message=" +        
                    "To%20use%2024hrsinSF%27s%20auto-location%20feature%2C%20you%27ll%20need%20to%20install%20gears" +
                    "&return=http%3A%2F%2F24hrsinsf.appspot.com%2Fmobile";
    }

  geo.getPosition(updatePosition, handleError, {enableHighAccuracy: true});
  return true;
        
}</pre>
<h3>Display the User Location</h3>
<p>If our call to the Gears API returns the user's location, the function<code>updatePosition</code> uses the lat/lon position returned by Gears and displays it with Google Maps. This requires us to initialize a Maps instance, and add an marker to the map at the user's position. This is done with the Javascript here:</p>
<pre class="prettyprint">function updatePosition(position) {
    lat = position.latitude;
    lon = position.longitude;
    var current_location = new GLatLng(lat, lon);
    geocoder = new GClientGeocoder();
    map = new GMap2(document.getElementById("map_canvas"));
    geocoder.getLocations(current_location, showAddress)
    old_overlay = current_location
    map.setCenter(current_location, 13);
    var marker = new GMarker(current_location);    
    map.addOverlay(marker);
}</pre>
<h3>Update the User's Location</h3>
<p>If Gears fails to find the user location, or the user wants to search somewhere other than his or her position, we also allow the user to specify an address.  Once the user enters their location in an HTML form, we can use the Google Maps <code>getLatLng</code> function to turn the human readable address in to a latitude and longitude:</p>
<pre class="prettyprint">function updateUserLocation(form){
  if (geocoder) {
    var loc = geocoder.getLatLng(
              form.address.value,
              function(point) {
                if(!point){
                    alert('Bad Address')
                    return;
                } else {
                  map.setCenter(point, 13);
                  var marker = new GMarker(point);
                  map.removeOverlay(old_overlay);
                  map.addOverlay(marker);
                  old_overlay = point;

                }
              }
            );
  }          
}</pre>
<p>This fairly simple Javascript is all we need to easily provide our users with a dynamic experience tailored to their location.</p>
<h2>Conclusion</h2>
<p>Now, I'll never be without an idea of where to go at 2 PM or 2 AM.  And we hope this enables you to develop great Geo apps for App Engine.  Here are some resources that will help you develop your application:
<ul>
<li><a href="http://code.google.com/apis/maps/">Google Maps API Documentation</a></li>
<li><a href="http://code.google.com/apis/gears/">Google Gears API Documentation</a></li>
<li><a href="http://code.google.com/p/geodatastore/">Google App Engine GeoDatastore Sample</a></li>
<li><a href="http://code.google.com/p/google-app-engine-samples">24 Hours in San Francisco Sample</a></li>
</ul>
</p>
</div>
</div>
   
      </div><!-- end gc-pagecontent -->
   </div><!-- end gooey wrapper -->

    </div> <!-- end codesite content -->

<div id="gc-footer" dir="ltr">
  <div class="text">
    
      <div class="notice"><div id="notice" style="text-align: center; border: 1em 0em 1em 0em">
  Except as otherwise <a
  href="http://code.google.com/policies.html#restrictions">noted</a>,
  the content of this page is licensed under the <a rel="license"
  href="http://creativecommons.org/licenses/by/2.5/">Creative Commons
  Attribution 2.5 License</a>, and code samples are licensed under the
  <a rel="license" href="http://www.apache.org/licenses/LICENSE-2.0">Apache
  2.0 License</a>.
<!-- <rdf:RDF xmlns="http://web.resource.org/cc/" 
              xmlns:dc="http://purl.org/dc/elements/1.1/"
              xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
  <Work rdf:about="">
    <license rdf:resource="http://creativecommons.org/licenses/by/2.5/" />
  </Work>
  <License rdf:about="http://creativecommons.org/licenses/by/2.5/">
    <permits rdf:resource="http://web.resource.org/cc/Reproduction"/>
    <permits rdf:resource="http://web.resource.org/cc/Distribution"/>
    <requires rdf:resource="http://web.resource.org/cc/Notice"/>
    <requires rdf:resource="http://web.resource.org/cc/Attribution"/>
    <permits rdf:resource="http://web.resource.org/cc/DerivativeWorks"/>
  </License>
</rdf:RDF> -->
</div>
Java is a registered trademark of Sun Microsystems, Inc.</div>
    
    &copy;2009 Google -
    <a href="http://code.google.com">Code Home</a> -
    <a href="http://www.google.com/accounts/TOS">Terms of Service</a> -
    <a href="http://www.google.com/privacy.html">Privacy Policy</a> -
    <a href="http://code.google.com/more">Site Directory</a>
    <br /> <br />
    Google Code offered in:
    <a href="http://code.google.com/intl/en">English</a> -
    <a href="http://code.google.com/intl/es">Español</a> -
    <a href="http://code.google.com/intl/ja">日本語</a> -
    <a href="http://code.google.com/intl/ko">한국어</a> -
    <a href="http://code.google.com/intl/pt-BR">Português</a> -
    <a href="http://code.google.com/intl/ru">Pусский</a> -
    <a href="http://code.google.com/intl/zh-CN">中文(简体)</a> -
    <a href="http://code.google.com/intl/zh-TW">中文(繁體)</a>
  </div>
</div><!-- end gc-footer -->

</div><!-- end gc-containter -->

<script type="text/javascript">CODESITE_CSITimer['load'].tick('ats');</script>
<script src="../../js/codesite_tail.pack.04102009.js" type="text/javascript"></script>






  </body>
</html>


